package cn.guyouda.algorithms.sort;

/**
 * 堆排序
 *
 * @author Youda
 */
public class HeapSort {

    private Comparable[] src;
    private int length;

    public HeapSort(Comparable[] src) {
        this.src = src;
        this.length = src.length;
    }

    /**
     * 调整二叉树
     * 如果父节点编号为x, 那么左子节点的编号是2x, 右子节点的编号是2x+1
     * 节点编号从1开始, 对应数组中的索引是编号-1
     *
     * @param nodeId 节点编号, 从1开始
     */
    public void adjust(int nodeId) {
        int swapId;
        int flag = 0; //是否需要继续向下调整
        while (nodeId * 2 <= this.length && flag == 0) {
            //首先判断它和左子节点的关系, 并用swapId记录值较小的节点编号(最大堆是记录较大的)
            int index = nodeId - 1; //节点对应数组中数字的索引
            int leftChild = nodeId * 2 - 1; //左子节点对应数组中数字的索引
            int rightChild = nodeId * 2; //右子节点对应数组中数字的索引
            if (less(src[index], src[leftChild])) {
                swapId = nodeId * 2;
            } else {
                swapId = nodeId;
            }
            //如果有右子节点, 再与右子节点比较
            if (nodeId * 2 + 1 <= this.length) {
                if (less(src[swapId - 1], src[rightChild]))
                    swapId = nodeId * 2 + 1;
            }
            //如果最小的节点编号不是自己, 说明子节点中有比父节点更小的
            if (swapId != nodeId) {
                swap(swapId, nodeId);
                nodeId = swapId;
            } else {
                flag = 1;
            }
        }
    }

    /**
     * 比较x是否小于y
     *
     * @param x
     * @param y
     * @return
     */
    public static boolean less(Comparable x, Comparable y) {
        return x.compareTo(y) < 0;
    }

    /**
     * 交换两个节点的值
     *
     * @param nodeId1
     * @param nodeId2
     */
    public void swap(int nodeId1, int nodeId2) {
        Comparable t = src[nodeId1 - 1];
        src[nodeId1 - 1] = src[nodeId2 - 1];
        src[nodeId2 - 1] = t;
    }

    /**
     * 创建最大堆
     */
    public void createMaxHeap() {
        //从最后一个非叶节点到第一个节点依次向上调整
        for (int i = this.length / 2; i >= 1; i--) {
            adjust(i);
        }
    }

    /**
     * 排序
     */
    public void sort() {
        while (this.length > 1) {
            swap(1, this.length);
            this.length--;
            adjust(1);
        }

    }

    public static void main(String[] args) {
        //测试数据
        String[] src1 = {"a", "x", "z", "i", "y", "o", "l", "q", "b", "d", "z", "s", "c"};
        Integer[] src2 = {100, 99, 70, 98, 99, 101, 3, 6, 676, 45, 25, 77, 80, 1, 0, 46, 28, 11111, 56666, 22, 6, 8, 29};

        System.out.println("===========原数组==========");
        for (String str : src1) {
            System.out.print(str + ",");
        }
        HeapSort heap1 = new HeapSort(src1);
        heap1.createMaxHeap();
        heap1.sort(); //排序

        System.out.println();
        System.out.println("==========排序后==========");
        for (String str : src1) {
            System.out.print(str + ",");
        }


        System.out.println();
        System.out.println("==========原数组=========");
        for (int i = 0; i < src2.length; i++) {
            System.out.print(src2[i] + ",");
        }

        HeapSort heap2 = new HeapSort(src2);
        heap2.createMaxHeap();
        heap2.sort(); //排序

        System.out.println();
        System.out.println("==========排序后==========");
        for (int i = 0; i < src2.length; i++) {
            System.out.print(src2[i] + ",");
        }
    }


}
